package ljl.alg.wangzheng_camp.round1.array_and_list;

import commons.ListNode;

public class _206_reverse_list {
    
    public ListNode reverseList1(ListNode head) {
        if (head == null) return null;
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    /**
     * 隔了一段时间
     * 这个递归解法让我非常的费解
     * */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 翻转除了 head 的部分，返回的应该是最末元素，用不了，只能返回
        ListNode newHead = reverseList(head.next);
        // 这个是把真的最末元素连到 head 上了
        head.next.next = head;
        // 这个断开当前的头和它的 next
        head.next = null;
        return newHead;
    }
}
